package class12;


/**
 * 两个字符串的最长公共子序列问题
 * 例子:
 * str1="ab1cd2ef345gh"
 * str2="opq123rs4tx5yz"
 * 最长公共子序列: "12345"
 *
 * 思路:
 * 1.比较的是两个字符串,那么把两个字符串具象为一张二维表
 * 2.x轴表示str1的下标,y轴表示str2的下标
 * 3.每个格子表示在(x,y)来截断原str,两个子序列中最长的公共子序列数
 *
 */
public class Code05_PalindromeSubsequence {

	public static int lcse(char[] str1, char[] str2) {
		
		
		
		
		int[][] dp = new int[str1.length][str2.length];
		
		
		//填充(0,0)的值
		dp[0][0] = str1[0] == str2[0] ? 1 : 0;
		
		//填充第0列的值
		for (int i = 1; i < str1.length; i++) {
			dp[i][0] = Math.max(dp[i - 1][0], str1[i] == str2[0] ? 1 : 0);
		}
		//填充第0行的值
		for (int j = 1; j < str2.length; j++) {
			dp[0][j] = Math.max(dp[0][j - 1], str1[0] == str2[j] ? 1 : 0);
		}
		//动态规划
		for (int i = 1; i < str1.length; i++) {
			for (int j = 1; j < str2.length; j++) {
				//情况1, (i,j)的最长公共子序列不以i结尾且不以j结尾, 比情况2/3小可以舍弃
				//情况2/3, (i,j)的最长公共子序列以i结尾不以j结尾, (i,j)的最长公共子序列以j结尾不以i结尾
				dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
				if (str1[i] == str2[j]) {
					//情况4, 只有当i,j两个字符相同时才可能出现
					//结果是: dp[i - 1][j - 1] + 1
					dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1] + 1);
				} 
			}
		}
		return dp[str1.length - 1][str2.length - 1];
	}

	public static void main(String[] args) {

	}

}
